package class03;

import java.util.Stack;

/**
 * 使用两个栈实现队列功能
 * 
 * 算法原理：
 * 队列的特点是先进先出(FIFO)，而栈的特点是后进先出(LIFO)。
 * 通过两个栈的配合使用，可以实现队列的功能：
 * 1. stackPush：用于接收新加入的元素（入队操作）
 * 2. stackPop：用于弹出最早加入的元素（出队操作）
 * 
 * 核心思想：
 * 当需要弹出元素时，将stackPush中的所有元素依次弹出并压入stackPop，
 * 这样stackPop中的元素顺序就与stackPush中的元素顺序相反，
 * 此时stackPop的栈顶元素就是最早加入的元素。
 * 
 * 时间复杂度分析：
 * - add操作：O(1)
 * - poll和peek操作：均摊时间复杂度O(1)
 * 
 * 空间复杂度：O(N)，其中N为队列中的元素个数
 */
public class Code06_TwoStacksImplementQueue {

	/**
	 * 双栈实现队列的数据结构
	 * 
	 * 设计思路：
	 * - stackPush：接收新加入的元素
	 * - stackPop：提供弹出和查看队首元素的功能
	 * 
	 * 数据转移策略：
	 * 当stackPop为空时，将stackPush中的所有元素转移到stackPop中
	 * 这样保证了队列的先进先出特性
	 */
	public static class TwoStacksQueue {
		public Stack<Integer> stackPush; // 用于接收新加入的元素（入队栈）
		public Stack<Integer> stackPop;  // 用于弹出队首元素（出队栈）

		/**
		 * 构造函数，初始化两个栈
		 */
		public TwoStacksQueue() {
			stackPush = new Stack<Integer>(); // 入队栈，接收新元素
			stackPop = new Stack<Integer>();  // 出队栈，提供队列的弹出功能
		}

		/**
		 * 将stackPush中的数据倒入stackPop中
		 * 
		 * 倒入条件：
		 * 只有当stackPop为空时才进行数据倒入操作，避免数据顺序混乱
		 * 
		 * 实现原理：
		 * 将stackPush中的元素逐个弹出并压入stackPop，实现顺序的反转
		 * 这样stackPop的栈顶元素就是最早加入的元素
		 */
		private void pushToPop() {
			if (stackPop.empty()) {
				// 当出队栈为空时，将入队栈的所有元素倒入出队栈
				while (!stackPush.empty()) {
					stackPop.push(stackPush.pop());
				}
			}
		}

		/**
		 * 向队列尾部添加元素（入队操作）
		 * 时间复杂度：O(1)
		 * 
		 * @param pushInt 要添加的整数元素
		 */
		public void add(int pushInt) {
			stackPush.push(pushInt); // 直接将元素压入入队栈
			pushToPop(); // 检查是否需要将数据倒入出队栈
		}

		/**
		 * 从队列头部移除并返回元素（出队操作）
		 * 均摊时间复杂度：O(1)
		 * 
		 * @return 队列头部的元素
		 * @throws RuntimeException 当队列为空时抛出异常
		 */
		public int poll() {
			if (stackPop.empty() && stackPush.empty()) {
				// 当两个栈都为空时，队列为空
				throw new RuntimeException("Queue is empty!");
			}
			pushToPop(); // 确保出队栈中有元素
			return stackPop.pop(); // 从出队栈弹出栈顶元素
		}

		/**
		 * 返回队列头部的元素但不移除它
		 * 均摊时间复杂度：O(1)
		 * 
		 * @return 队列头部的元素
		 * @throws RuntimeException 当队列为空时抛出异常
		 */
		public int peek() {
			if (stackPop.empty() && stackPush.empty()) {
				// 当两个栈都为空时，队列为空
				throw new RuntimeException("Queue is empty!");
			}
			pushToPop(); // 确保出队栈中有元素
			return stackPop.peek(); // 查看出队栈的栈顶元素
		}
	}

	public static void main(String[] args) {
		TwoStacksQueue test = new TwoStacksQueue();
		test.add(1);
		test.add(2);
		test.add(3);
		System.out.println(test.peek());
		System.out.println(test.poll());
		System.out.println(test.peek());
		System.out.println(test.poll());
		System.out.println(test.peek());
		System.out.println(test.poll());
	}

}